package cn.edu.hit.fft;

public class FFTJ {
    // compute the FFT of x[], assuming its length is a power of 2
    public static Complex[] fftj(Complex[] x) {
        int N = x.length;

        // base case
        if (N == 1) return new Complex[]{x[0]};

        // radix 2 Cooley-Tukey FFT
        if (N % 2 != 0) {
            throw new RuntimeException("N is not a power of 2");
        }

        // fft of even terms
        Complex[] even = new Complex[N / 2];
        for (int k = 0; k < N / 2; k++) {
            even[k] = x[2 * k];
        }
        Complex[] q = fftj(even);

        // fft of odd terms
        Complex[] odd = even;  // reuse the array
        for (int k = 0; k < N / 2; k++) {
            odd[k] = x[2 * k + 1];
        }
        Complex[] r = fftj(odd);

        // combine
        Complex[] y = new Complex[N];
        for (int k = 0; k < N / 2; k++) {
            double kth = -2 * k * Math.PI / N;
            Complex wk = new Complex(Math.cos(kth), Math.sin(kth));
            y[k] = q[k].addtion(wk.multiplication(r[k]));
            y[k + N / 2] = q[k].subtraction(wk.multiplication(r[k]));
        }


        return y;
    }

    public static double[] fft(Complex[] source) {
        int n = source.length;
        Complex[] fftr = new Complex[n];
        fftr = fftj(source);
        double[] result = new double[n];
        for (int i = 0; i < n; ++i) {
            result[i] = fftr[i].abs() * 2 / n;
        }
        result[0] = 0;
        return result;
    }
}

